package Q1049;

/**
 * 最后一块石头的重量
 * @author 23737
 * @time 2021.11.25
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().lastStoneWeightII(new int[]{2, 7, 4, 1, 8, 1}));
    }
}

/**
 * 动态规划--此题可以拆解为分割等和子数组的问题
 */
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int length = stones.length;
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum >> 1;

        //define
        int[] dp = new int[target+1];

        //init and sp
        for (int i = 0; i < length; i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return sum - 2*dp[target];
    }
}

